#include "MinHeap.h"
void MinHeap::heapify(int i)
{
	int l=left(i), r=right(i),min=i;
	HeapLink* tmp;
	
	if (l<_heapSize-1  && _arr[l]->num < _arr[i]->num)
		min=l;
	
	if (r<_heapSize-1  && _arr[r]->num < _arr[min]->num)
		min=r;
	
	if (min!=i)
	{
		swap(_arr,i,min);
		heapify(min);
	}
}

void MinHeap::insert(int c){
	_heapSize++;
	HeapLink* link = new HeapLink(c,0);
	_arr.push_back(link);
	link->pos=_heapSize-1;
	int i = _heapSize-1;

	while(i>0 && _arr[parent(i)]->num > _arr[i]->num)
	{
		swap(_arr,i,parent(i));
		i=parent(i);
	}
}

void MinHeap::swap(vector<HeapLink* >&  arr, int i,int j){
	HeapLink* tmp1 = arr[i], *tmp2 = arr[j];
	arr.erase(arr.begin() + j);
	arr.insert(arr.begin() + j,tmp1);
	arr.erase(arr.begin() + i);
	arr.insert(arr.begin() + i,tmp2);

	arr[i]->pos = i;
	arr[j]->pos = j;
}

void MinHeap::posIT(HeapLink* tmp,int index){
	tmp->pos = index;
}

int MinHeap::popMin()
{
	if (isEmpty())
		return -1;
	return extract(0);
}
